#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>


using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
	unordered_map<int,int> pos = {};
	
    TreeNode* constructMaximumBinaryTree1(vector<int>& nums) {
		for(int i = 0; i < nums.size(); i++){
			pos[nums[i]] = i;
		}
		return dfs(nums, 0, nums.size());
    }
	
	TreeNode * dfs(vector<int>& nums, int left, int right){
		if(left >= right) return nullptr;
		int maxNum = *max_element(nums.begin() + left, nums.begin() + right);
		TreeNode * node = new TreeNode(maxNum);
		int index = pos[maxNum];
		node->right = dfs(nums, index + 1, right);
		node->left = dfs(nums, left, index);
		return node;
	}
	
	// {3,2,1,6,0,5};
	TreeNode* constructMaximumBinaryTree2(vector<int>& nums) {
		vector<TreeNode *> st;
		for(auto i : nums){
			TreeNode * node = new TreeNode(i);
			if(st.empty()){

			}else if(i < st.back()->val){
				st.back()->right = node;
			}else{
				TreeNode * top = nullptr;
				while(!st.empty()){
					top = st.back();
					if(st.back()->val > i){
						break;
					}else{
						st.pop_back();
					}
				}
				if(st.empty()){
					node->left = top;
				}else{
					node->left = top->right;
					top->right = node;
				}
			}
			st.push_back(node);
		}
		return st[0];
    }
	
	
	TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
		vector<TreeNode *> st;
		for(auto i : nums){
			TreeNode * node = new TreeNode(i);
			if(!st.empty() && i > st.back()->val){
				TreeNode * back = nullptr;
				while(!st.empty() && st.back()->val < i){
					back = st.back();
					st.pop_back();
				}
				if(st.empty()){
					node->left = back;
				}else{
					node->left = st.back()->right;
					st.back()->right = node;
				}
			}else if(!st.empty()){
				st.back()->right = node;
			}
			
			st.push_back(node);
		}
		return st[0];
    }
	
	
	
	void show(TreeNode* node){
		if(!node) return;
		show(node->left);
		cout << node->val << ",";
		show(node->right);
	}
};

int main(){
	Solution so;
	vector<int> nums = {3,2,1,6,0,5};
	TreeNode* node = so.constructMaximumBinaryTree(nums);
	so.show(node);
	return 0;
}